package com.wtgroup.demo.leetcode.q120_三角形最小路径和;

import java.util.List;

/**
 * @author 60906
 * @date 2021/5/11 14:11
 */
public class Q120 {

    /**
     * 备忘录方式, 重叠的缓存.
     * 效率: 96%.
     * 暴力递归, 超时.
     */
    private class Solution_MyDp {

        public int minimumTotal(List<List<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0) {
                return 0;
            }
            int[][] dp = new int[triangle.size()][triangle.get(triangle.size() - 1).size()];
            for (int i = 0; i < dp.length; i++) {
                for (int j = 0; j < dp[i].length; j++) {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
            return func(triangle, 0, 0, dp);
        }

        int func(List<List<Integer>> triangle, int curLvl, int curIx, int[][] dp) {
            if (curLvl == triangle.size()) {
                return 0; // 最后一层, dp 里没有
            }
            if (dp[curLvl][curIx] != Integer.MAX_VALUE) {
                return dp[curLvl][curIx];
            }

            int left = func(triangle, curLvl + 1, curIx, dp);
            int right = func(triangle, curLvl + 1, curIx + 1, dp);

            return dp[curLvl][curIx] = triangle.get(curLvl).get(curIx) + Math.min(left, right);
        }
    }

    /**
     * 打表, 数组压缩.
     *
     * 状态转移公式: dp[i][j] = min(dp[j], dp[j+1]) + data[i][j]
     *
     * 内存: 88%; 时间: 96%;
     */
    class Solution_MyDp2 {
        public int minimumTotal(List<List<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0) {
                return 0;
            }

            int[] dp = new int[triangle.get(triangle.size() - 1).size() + 1]; // 最底层长度+1个
            // 从底层往上层推
            for (int i = triangle.size() - 1; i >= 0; --i) {
                // 从左向右覆盖
                List<Integer> line = triangle.get(i);
                for (int j = 0; j < line.size(); j++) {
                    dp[j] = Math.min(dp[j], dp[j + 1]) + line.get(j);
                }
            }

            return dp[0];
        }
    }
}
